The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay. Our analysis also reveals an intriguing phenomenon: the approximation factor as a function of k may exhibit multiple peaks and valleys, which we call a multiple-descent curve. A lower bound we establish shows that this behavior is not an artifact of our analysis, but rather it is an inherent property of the CSSP and Nystrom tasks. Finally, using the example of a radial basis function (RBF) kernel, we show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.

While the original algorithm was slow, efficient implementations have been provided since then (e.g., see

Lemma 5 implies a simple closed form expression for the expected error in the CSSP . Using Lemma 5, the expected loss is given by: E " Er We will use the following standard determinantal summation identity (see Theorem 2.1 in Kulesza & Lemma 7. F or any n ˆ n matrix K, we have det p I ` K q" ÿ We now proceed with the proof of Lemma 5 (restated below for convenience). We will next define an alternate sequence of eigenvalues which is in some sense "worst-case", by " r l, and obtain: ÿ Newton's inequalities imply that: 1 e The results of Deshpande et al. ( 2006) and Guruswami & Sinop ( 2012) establish that A q and we let b " min t k s, n k u, then for any 0 Now, the result follows easily by invoking Lemma 3: E " Er We provide the proof by splitting it into two cases. Further using u " k s, we can call upon Theorem 1 to get, With p k { 60, we get: 12 pk k 2 p 12 pk k k { 30 " 12 p 1 1 { 30 360 29 p. The overall bound thus becomes 61 p . We will use u " k s .

The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay. Our analysis also reveals an intriguing phenomenon: the approximation factor as a function of k may exhibit multiple peaks and valleys, which we call a multiple-descent curve.

The winners of the NeurIPS 2020 awards have been announced. This year, three papers have received Best Paper Awards. There was also one Test of Time Award; this recognises a paper that has had significant and lasting impact on the community. No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium Andrea Celli, Alberto Marchesi, Gabriele Farina, Nicola Gatti Abstract: The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium.

The Column Subset Selection Problem (CSSP) and the Nystr\"om method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay. Our analysis also reveals an intriguing phenomenon: the approximation factor as a function of k may exhibit multiple peaks and valleys, which we call a multiple-descent curve. A lower bound we establish shows that this behavior is not an artifact of our analysis, but rather it is an inherent property of the CSSP and Nystr\"om tasks. Finally, using the example of a radial basis function (RBF) kernel, we show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.